import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/11 16:09
 * @description 二维数组的前缀和
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[][] mat = {{1,2,3}, {4, 5,6}, {7, 8,9}};
        solution2.matrixBlockSum(mat, 1);
    }
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] res = new int[m][n];
        // 前缀和
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 左上角坐标
                int r1 = Math.max(i - k, 0);
                int c1 = Math.max(j - k, 0);

                // 右下角坐标
                int r2 = Math.min(i + k, m-1);
                int c2 = Math.min(j + k, n-1);

                // 包含右下角的所有和为 dp[r2+1][c2+1], 需要减去左上角左边的所有列和， 减去左上角上边的所有行和 + 多减的
                res[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1];
            }
        }
        return res;
    }
}
